package leetcode100

// TODO 动态规划 | 状态转移方程 [经典] 【-】 最大子数组和
// TODO https://leetcode.cn/problems/maximum-subarray/?favorite=2cktkvj

func maxSubArray(nums []int) int {
	// 一看都是dp, 虽然题目是中等题，但是从dp角度看就是个简单的题目，是一个值得记忆的题目，因为框架特别明晰
	n := len(nums)
	// dp[i]表示，前i个元素最大连续子数组和，包含nums[i]元素
	// 声明dp, 初始化dp[0], maxSum
	dp := make([]int, n)
	dp[0] = nums[0]
	maxSum := nums[0]
	for i := 1; i < n; i++ {
		// 理清楚，如何得到前i个元素的最大值，这个逻辑算是简单的了
		dp[i] = max2(dp[i-1]+nums[i], nums[i])
		maxSum = max2(maxSum, dp[i])
	}
	return maxSum
}
func max2(a, b int) int {
	if a > b {
		return a
	}
	return b
}
